#include <bits/stdc++.h>
using namespace std;

/*
2221. 数组的三角和
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
将 newNums 替换 数组 nums 。
从步骤 1 开始 重复 整个过程。
请你返回 nums 的三角和。

 

示例 1：



输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。
示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。
 

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 9
*/

// 法一
class Solution {
public:
    int triangularSum(vector<int>& nums) {
        // 只有一个就直接返回元素
        int n = nums.size();
        while (n > 1) {
            // new array
            vector<int> newNums(n - 1);
            for (int i = 0; i < n - 1; i++) {
                newNums[i] = (nums[i] + nums[i + 1]) % 10;
            }
            // update arr --> newArr
            nums = newNums;
            n = nums.size();
        }
        // 最后剩的唯一就是三角形
        return nums[0];
    }
};

// 法二
// 三角和的数学性质  sum(nums[i] * C(n-1,i) mod 10)   C(n-1,i) 是组合数  O (n)
// 自定义的实现 快速幂
using ll = long long;

// fast pow
ll fastPow(ll base, ll index, ll mod) {
    if (index == 0) return 1;
    if (index == 1 || base <= 1) return base;

    ll ans = 1;
    while (index > 0) {
        if ((index & 1) == 1)   ans = ans * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return ans;
}

// Lucas定理 模运算 大组合数
class Combination {
private: 
    int _maxN, _mod;          // 最大n值、模值
    vector<ll> _fact, _inFact; // 阶乘、阶乘逆元数组
    bool _modIsPrime;         // 模是否为质数（用于Lucas定理）
    int _effectiveN;          // 有效计算范围（模不为0时取min(maxN, mod-1)）

    // 直接计算组合数
    int _directCombine(int n, int k) {
        ll ans = _fact[n] * _inFact[k];
        if (_mod)       ans %= _mod;
        ans *= _inFact[n - k];
        if (_mod)       ans %= _mod;
        return ans;
    }

    // 大组合数
    ll _lucas(ll n, ll k) {
        ll ans = 1;
        while (n || k) {
            int ni = n % _mod;
            int ki = k % _mod;
            if (ki > ni)    return 0;
            ans = (ll)ans * _directCombine(ni, ki) % _mod;
            n /= _mod;
            k /= _mod;
        }
        return ans;
    }

public: 
    Combination(int n, int mod = 0) : _maxN(n), _mod(mod) {
        if (_mod == 0 && _maxN > 20)        throw invalid_argument("不设置余数时, n不能大于20（避免溢出）");
        if (_mod > 1) {
            _modIsPrime = _is_prime(_mod);
            _effectiveN = min(_maxN, _mod - 1); // 模为质数时，阶乘循环到mod-1
        } else {
            _modIsPrime = false;
            _effectiveN = _maxN;
        }
        _fact.resize(_effectiveN + 1, 0);
        _inFact.resize(_effectiveN + 1, 0);
        init(); // 初始化阶乘和逆元
    }

    // check 质数  是否可用lucas
    bool _is_prime(int p) {
        if (p < 2)  return false;
        for (int i = 2; i * i <= p; i++) {
            if (p % i == 0)     return false;
        }
        return true;
    }

    // init(); // 初始化阶乘和逆元
    void init() {
        if (_mod == 1) return ;
        _fact[0] = 1;

        // caculate 阶乘
        for (int i = 1; i <= _effectiveN; i++) {
            // 计算阶乘 fact[i] = i! mod mod
            _fact[i] = _fact[i - 1] * i;
            if (_mod) _fact[i] %= _mod;
        }
        // 逆元 费马小定理  inFact[n] = (fact[n])^(mod-2) mod mod
        if (_mod > 1) {
            _inFact[_effectiveN] = fastPow(_fact[_effectiveN], _mod - 2, _mod);
            for (int i = _effectiveN; i >= 1; i--) {
                // 逆元递推：inFact[i-1] = inFact[i] * i mod mod
                _inFact[i - 1] = _inFact[i] * i;
                if (_mod) _inFact[i - 1] %= _mod;
            }
        }
    }

    // 组合数  模是否为质数选择直接计算或Lucas定理
    ll combine(int n, int k) {
        if (n < k || n < 0 || k < 0)        return 0;
        if (_mod == 1)                      return 0;

        if (n > _maxN)                      throw "n超出最大范围";

        if (n < _mod)                       return _directCombine(n, k); // n小于模时直接计算
        else if (_modIsPrime)               return _lucas(n, k); // 模为质数且n较大时用Lucas定理
        else                                return 0; // 模非质数且n较大时不支持（本题中模为2和5，均为质数）
    }

};

class Solution {
public:
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    
    int triangularSum(vector<int>& nums) {
        // 只有一个就直接返回元素
        int n = nums.size();
        int ans = 0;

        // 系数和  C(n-1, i) mod 10
        Combination comb2(n - 1, 2);  // 计算C(n-1,i) mod 2
        Combination comb5(n - 1, 5);  // 计算C(n-1,i) mod 5
        for (int i = 0; i <= n - 1; i++) {
            ll c2 = comb2.combine(n - 1, i); // C(n-1,i) mod 2
            ll c5 = comb5.combine(n - 1, i); // C(n-1,i) mod 5
            // 中国剩余定理合并：找x满足x≡c2 mod2且x≡c5 mod5，解为(5*c2 + 6*c5) mod10
            int coeff = (5 * c2 + 6 * c5) % 10; 
            ans = (ans + coeff * nums[i]) % 10; // 累加每个元素×系数的结果
        }
        return ans;
    }
};